package nowcoder.all;

public class NC127 {

    public String LCS (String str1, String str2) {
        // write code here
        int len1 = str1.length(), len2 = str2.length();
        int[][] dp = new int[len1][len2];
        int maxLen = 0, maxIdx = 0; //最长公共字串长度以及此字串结束位置在str1的下标
        //init
        for (int i = 0; i < len1; i++) {
            dp[i][0] = str1.charAt(i)==str2.charAt(0)?1:0;
            if(maxLen<dp[i][0]){
                maxLen = dp[i][0];
                maxIdx = i;
            }
        }
        for (int j = 0; j < len2; j++) {
            dp[0][j] = str1.charAt(0)==str2.charAt(0)?1:0;
            if(maxLen<dp[0][j]){
                maxLen = dp[0][j];
                maxIdx = 0;
            }
        }
        //dp
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                dp[i][j] = str1.charAt(i)==str2.charAt(j)?dp[i-1][j-1]+1:0;
                if(maxLen<dp[i][j]){
                    maxLen = dp[i][j];
                    maxIdx = i;
                }
            }
        }
        //
        return str1.substring(maxIdx+1-maxLen,maxIdx+1);
    }
}
